package com.hy;

import java.util.ArrayDeque;
import java.util.Arrays;

/**
 * Created With IntelliJ IDEA.
 * Descriptions:最短无序连续子数组
 *
 * 给你一个整数数组 nums ，你需要找出一个 连续子数组 ，如果对这个子数组进行升序排序，那么整个数组都会变为升序排序。
 *
 * 请你找出符合题意的 最短 子数组，并输出它的长度。
 *
 *
 * author: Mr.Du
 * Date: 2023/12/19
 * Time: 9:59
 */
public class FindUnsortedSubarray {


    /**
     * 先找出左右的升序边界(0,l),(r,nums.length-1)
     *
     * @param nums
     * @return
     */
    public int findUnsortedSubarray(int[] nums) {
        int l = 0, r = nums.length - 1,n = nums.length;
        while(l < r && nums[l] <= nums[l + 1]) l++;
        while(l < r && nums[r] >= nums[r-1]) r--;
        int i = l, j = r;
        for(int k = i;k <= j;k++){
            while(l >= 1 && nums[k] < nums[l-1]) l--;
            while(r < n - 1 && nums[k] > nums[r+1]) r++;
        }
        return l == r ? 0 :r - l + 1;
    }


    /**
     * 排序做法
     * @param nums
     * @return
     */
    public int findUnsortedSubarray1(int[] nums) {
        int[] res = Arrays.copyOf(nums, nums.length);
        Arrays.sort(res);
        int l = 0, r = nums.length - 1;
        while(l < r){
            if(res[l] == nums[l] && res[r] == nums[r]){
                l++;
                r--;
            }else if(res[l] != nums[l] && res[r] == nums[r]){
                r--;
            }else if(res[l] == nums[l] && res[r] != nums[r]){
                l++;
            }else{
                return r - l + 1;
            }
        }
        return 0;
    }
}
